package LCR;

public class partition {
    public ListNode partition(ListNode head, int x) {
        ListNode list2 = new ListNode(0);
        ListNode list1 = new ListNode(0);
        ListNode ret1 = list1;
        ListNode ret2 = list2;
        while (head != null) {
            if (head.val < x) {
                list1.next = head;
                list1 = list1.next;
            } else {
                list2.next = head;
                list2 = list2.next;
            }
            head = head.next;
        }
        list2.next = null;
        list1.next = ret2.next;
        return ret1.next;

    }
}
